/*
 * Algorithm.hpp
 *
 *  Created on: 02.10.2012
 *      Author: dom
 */

#ifndef ALGORITHM_HPP_
#define ALGORITHM_HPP_

#include <stdlib.h>
#include <cmath>
#include <map>
#include <limits>

namespace mpei {

const uint8_t kEuckid = 2;
const uint8_t kPow = kEuckid;

template<typename _T, typename _D>
class ClassCount {

public:
	inline void operator()(_T* algo, _T* other) {
		if (!algo || !other) {
			return;
		}
		if (algo->getClassName() != other->getClassName()) {
			// документ не отнесен к классу Qk
			++count_false;
		} else {
			// документ отнесен к классу Qk
			++count_true;
		}
	}
	_D error() {
//		std::cout << "true: " << count_true << " false: " << count_false
//				<< std::endl;
		return count_false / (count_true + count_false);
	}
private:
	_D count_false;
	_D count_true;
};

class Algorithm {

public:

	template<typename _Class, typename _II, typename _E, typename _T,
			typename _OI = std::map<double, _E, std::greater<double>>,
			typename _S = std::string>
	static _Class * kNN(_II __first, _II __last, _E __other, _T numN) {

		typedef typename _II::value_type value_type;
		typedef typename _OI::mapped_type mapped_type;
		typedef typename _OI::key_type key_type;
		typedef typename _OI::value_type map_value_type;

//	auto result_ = _OI();
		auto map = _OI();
		_T find_neighbors_ = 0;
		while (__first != __last) {
			if ((*__first) == __other) {
				continue;
			}
			key_type distance_ = distance<key_type>((*__first), __other);
//		for (auto neigh : map) {
//			std::cout << "name " << neigh.second->getDocumentName()
//			<< " distance " << neigh.first << std::endl;
//		}
			if (find_neighbors_ < numN) {
				map.insert(map_value_type(distance_, (*__first)));
				++find_neighbors_;
//			std::cout << "add to neighbors: " << (*__first)->getDocumentName()
//			<< "Distance :" << distance_ << std::endl;
			} else {
				auto erase_ = map.begin();
				if (distance_ < erase_->first) {
					map.erase(erase_);
//				std::cout << "erase neighbor : "
//				<< erase_->second->getDocumentName() << std::endl;
					map.insert(map_value_type(distance_, (*__first)));
//				std::cout << "add to neighbors: " << (*__first)->getDocumentName()
//				<< "Distance :" << distance_ << std::endl;
				}
			}
			++__first;
		}
		auto classes_ = std::map<_S, int>();
		for (auto neighbor : map) {
			classes_[neighbor.second->getDocumentClass()->getClassName()]++;
		}
		auto classes_sort = std::map<int, _S, std::greater<int>>();
		for (auto neighbor : classes_) {
			classes_sort.insert(
					std::pair<int, _S>(neighbor.second, neighbor.first));
		}
//		for (auto neighbor : classes_) {
//			std::cout << "class " << neighbor.first << " count " << neighbor.second
//					<< std::endl;
//		}

		for (auto neighbor : map) {
			if (classes_sort.begin()->second
					== neighbor.second->getDocumentClass()->getClassName()) {
				return neighbor.second->getDocumentClass();
			}
		}
		std::cout << "error KNN" << std::endl;
		return nullptr;
	}

	template<typename _II, typename _C, typename _D = double>
	static void kMNN_train(_II __first, _II __last, _C centroids) {
		typedef typename _II::value_type value_type;
		typedef std::pair<_D, value_type> pair;
		for (auto centroid : centroids) {
			auto tmp_ = __first;
			for (; tmp_ != __last; ++tmp_) {
				auto doc = *tmp_;
				auto distance_ = distance<_D>(centroid, doc);
				centroid->setDistance(doc, distance_);
				doc->setDistanceToMean(centroid.get(), distance_);
				auto dist_test_ = doc->getDistanceToMean(centroid.get());
				if (dist_test_ != distance_) {
					std::cout << "name " << centroid->getDocumentName()
							<< " distance " << distance_ << " dist_test "
							<< dist_test_ << std::endl;
					throw std::logic_error("Wrong distance");
				}
			}
		}
	}

	template<typename Class, typename _II, typename E, typename C, typename _T,
			typename D = double, typename _S = std::string>
	static Class * kMNN(_II __first, _II __last, E __other, C centroids,
			_T numN) {
		typedef typename _II::value_type value_type;

		for (auto centroid : centroids) {
			auto distance_ = distance<D>(centroid, __other);

//			std::cout << "kMNN" << std::endl;
//			std::cout << "name: " << __other->getDocumentName() << " distance: "
//					<< distance_ << std::endl;
//			std::cout << "centroid: " << centroid->getDocumentName()
//					<< std::endl;

			centroid->findRadius(distance_);
		}

		std::set<value_type> NN;
		uint64_t index = 1;
		bool complete = false;
		while (!complete) {
			std::set<value_type> docs;
			for (auto centroid : centroids) {
				auto vector_ = centroid->getDocDelta(index);
				docs.insert(vector_.begin(), vector_.end());
			}
			auto tmp_ = docs.begin();
			for (; tmp_ != docs.end(); ++tmp_) {
				size_t i = 0;
				for (auto centroid : centroids) {
					auto radius = centroid->getRadius();
//					auto distance = tmp_->first;
					auto distance = (*tmp_)->getDistanceToMean(centroid.get());

					auto delta = centroid->getRadiusDelta(index);
					if (distance > radius && distance < delta) {
//						std::cout << "docs: " << (*tmp_)->getDocumentName()
//								<< " : "
//								<< (*tmp_)->getDistanceToMean(centroid.get())
//								<< std::endl;
						++i;
					} else {
						break;
					}
				}
				if (i == centroids.size()) {
//					std::cout << (*tmp_)->getDocumentClass()->getClassName()
//							<< std::endl;
					NN.insert(*tmp_);
				}
			}
			size_t size_ = NN.size();
			if (size_ < numN) {
				++index;
			} else {
				complete = true;
			}
			if (index == 50) {
				complete = true;
			}
		}

		if (!NN.size()) {
			std::cout << "no NN" << std::endl;
			return nullptr;
		}
		auto classes_ = std::map<_S, int>();
		for (auto neighbor : NN) {
//			std::cout << neighbor->getDocumentClass()->getClassName()
//					<< std::endl;
			classes_[neighbor->getDocumentClass()->getClassName()]++;
		}

		auto classes_sort = std::map<int, _S, std::greater<int>>();
		for (auto neighbor : classes_) {
			classes_sort.insert(
					std::pair<int, _S>(neighbor.second, neighbor.first));
		}
		for (auto neighbor : NN) {
			if (classes_sort.begin()->second
					== neighbor->getDocumentClass()->getClassName()) {
				return neighbor->getDocumentClass();
			}
		}
		std::cout << "error kMNN" << std::endl;
		return nullptr;
	}

	template<typename _Class, typename _II, typename _E, typename _D = double>
	static _Class * centroid(_II __first, _II __last, _E __other) {
		_D distance_min_ = std::numeric_limits<_D>::max();
		_Class * result = nullptr;
		while (__first != __last) {
			auto centroid_ = (*__first)->getCentroid();
			auto distance_ = distance<_D>(centroid_, __other);
//		std::cout << "Distance: " <<distance_ << std::endl;
			if (distance_ < distance_min_) {
				distance_min_ = distance_;
				result = centroid_->getDocumentClass();
			}
			++__first;
		}
		return result;
	}

	template<typename _Class, typename _II, typename _E, typename _K = size_t,
			typename _D = double>
	static _Class * naive_bayes(_II __first, _II __last, _E __other,
			_K doc_size) {
		_Class * result = nullptr;
		_D p_max_ = 0;
		while (__first != __last) {
			_K size_ = (*__first)->get().size();
			_D p_c = (_D) size_ / doc_size;
			auto tf_tokens_ = (*__first)->getTokensTf();
			_D sum = 0;
			for (auto all_token_ : tf_tokens_) {
//			std::cout << "sum"<<sum << std::endl;
				sum += all_token_.second;
			}
			for (auto token_other : __other->get()) {
				auto it = tf_tokens_.find(token_other->data());
				_D tf_other = 0;
				if (it != tf_tokens_.end()) {
					tf_other = it->second;
//				std::cout << "tf_other "<< tf_other << std::endl;
				}
				_D tmp_ = (tf_other + 1) / (sum + tf_tokens_.size());
//			std::cout << "tmp_"<< tmp_ << std::endl;
				p_c *= tmp_;
//			std::cout << "p_t_c "<< p_c << std::endl;
			}
			_D c = p_c;
			if (c > p_max_) {
				p_max_ = c;
//			std::cout << "p_max_"<< p_max_ << std::endl;
				result = (*__first).get();
			}
			++__first;
		}
		return result;
	}
private:
	/*
	 * euclidean specialization //TODO universal
	 */
	template<typename _T, typename _E>
	static inline _T distance(_E __first, _E __other) {
		typedef typename _E::element_type value;
		typedef typename _E::element_type::value_shared_ptr value_type;
		_T result_ = 0;
		auto tokens_first_ = __first->get();
		for (auto token_ : __other->get()) {
			auto it_ = std::find(tokens_first_.begin(), tokens_first_.end(),
					token_);
			if (it_ != tokens_first_.end()) {
//				result_ += std::pow(token_->getTfIdf() - (*it_)->getTfIdf(), 2);
				result_ += std::pow(token_->getTf() - (*it_)->getTf(), 2);
			} else {
//				result_ += std::pow(token_->getTfIdf(), 2);
				result_ += std::pow(token_->getTf(), 2);
			}
		}
		return std::sqrt(result_);
	}

};

class ConverterUtf8 {

public:
	std::wstring operator()(const std::string & src) {
		std::wstring dest;
		wchar_t w = 0;
		uint8_t bytes = 0;
		wchar_t err = L'�';
		for (size_t i = 0; i < src.size(); i++) {
			unsigned char c = (unsigned char) src[i];
			if (c <= 0x7f) { //first byte
				if (bytes) {
					dest.push_back(err);
					bytes = 0;
				}
				dest.push_back((wchar_t) c);
			} else if (c <= 0xbf) { //second/third/etc byte
				if (bytes) {
					w = ((w << 6) | (c & 0x3f));
					bytes--;
					if (bytes == 0)
						dest.push_back(w);
				} else
					dest.push_back(err);
			} else if (c <= 0xdf) { //2byte sequence start
				bytes = 1;
				w = c & 0x1f;
			} else if (c <= 0xef) { //3byte sequence start
				bytes = 2;
				w = c & 0x0f;
			} else if (c <= 0xf7) { //3byte sequence start
				bytes = 3;
				w = c & 0x07;
			} else {
				dest.push_back(err);
				bytes = 0;
			}
		}
		if (bytes)
			dest.push_back(err);
		return dest;
	}

	std::string operator()(const std::wstring & src) {
		std::string dest;
		for (size_t i = 0; i < src.size(); i++) {
			wchar_t w = src[i];
			if (w <= 0x7f)
				dest.push_back((char) w);
			else if (w <= 0x7ff) {
				dest.push_back(0xc0 | ((w >> 6) & 0x1f));
				dest.push_back(0x80 | (w & 0x3f));
			} else if (w <= 0xffff) {
				dest.push_back(0xe0 | ((w >> 12) & 0x0f));
				dest.push_back(0x80 | ((w >> 6) & 0x3f));
				dest.push_back(0x80 | (w & 0x3f));
			} else if (w <= 0x10ffff) {
				dest.push_back(0xf0 | ((w >> 18) & 0x07));
				dest.push_back(0x80 | ((w >> 12) & 0x3f));
				dest.push_back(0x80 | ((w >> 6) & 0x3f));
				dest.push_back(0x80 | (w & 0x3f));
			} else
				dest.push_back('?');
		}
		return dest;
	}

};

} // namespace mpei

#endif /* ALGORITHM_HPP_ */
